package Offer;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 队列的最大值
 * 维护一个单调的双端队列
 * 本算法基于问题的一个重要性质：当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响。
 * 举个例子，如果我们向队列中插入数字序列 1 1 1 1 2，那么在第一个数字 2 被插入后，数字 2 前面的所有数字 1 将不会对结果产生影响。
 * 因为按照队列的取出顺序，数字 2 只能在所有的数字 1 被取出之后才能被取出，因此如果数字 1 如果在队列中，
 * 那么数字 2 必然也在队列中，使得数字 1 对结果没有影响。
 * @author 是阿秋啊
 * @date 2022/08/16 19:28
 **/
public class Num59 {
    Deque<Integer> queue = new ArrayDeque<>();
    Deque<Integer> max_queue = new ArrayDeque<>();


    public int max_value() {
        if(queue.isEmpty()){
            return -1;
        }
        return max_queue.peekFirst();
    }

    public void push_back(int value) {
        while(!max_queue.isEmpty() && max_queue.peekLast() < value){
            max_queue.pollLast();
        }
        max_queue.offer(value);
        queue.offer(value);
    }

    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        int tmp = queue.poll();
        if(tmp == max_queue.peek()) {
            max_queue.poll();
        }
        return tmp;
    }
}